package com.qf.day14;

import java.util.HashMap;

public class HashmapInterview {
    /**
     * 面试题：请说说Hashmap的底层工作原理
     *
     * Hashmap底层的数据结构是：数组+链表+红黑树
     *
     * 1. 数组的长度？ 数组的初始长度？怎么扩容
     *    如果是调用无参构造，那么初始底层数组为null
     *    当put第一个key，value的时候，会把底层数组初始化为16
     *    （扩容的情形1）元素的容量超过了 16*0.75，就扩容
     *    （扩容的情形2）当链表的长度超过8，但是底层数组的长度不足64时，也会触发扩容
     *
     *    扩容的一些细节：
     *    (1) 底层数组的长度会变为原来的两倍
     *    (2) 在扩容之后，会重新分配数组中的元素，如果某个位置已经形成了链表，那么在扩容过程中，会把链表拆开，一部分放在地区，一部分放在高区
     *    (3) 扩容之后，当查询时，原来hash冲突的key在新数组的长度下计算hash值时，只有两种可能，要么跟原来的数组下标相同，要等于原来的数组下标+原数组长度
     *
     * 2. 键值对在hashmap内部是如何表示的？   Node对象 {key的hash值，key，value，next}
     * 3. 键值对是如何存放到数组中的？  根据key的hash值，计算出元素的数组下标 (底层数组长度 - 1) & hash 等价于hash对数组长度取模
     *    如果数组中当前的下标位置没有元素时，就直接放入该位置了。
     *
     * 4. （hash冲突）如何出现数组下标已经被元素占用的情况，那么新插入的键值对应该如何存放呢？  形成链表（连地址法解决hash冲突）
     *
     * 5. 什么情况下会出现链表呢？  当出现hash冲突时，会出现链表
     *
     * 6. 红黑树是什么情况下出现的呢？
     *    (条件1)当链表中的元素的数量超过 TREEIFY_THRESHOLD=8 时，就会将链表进行树化，把链表转换为红黑树
     *    (条件2) 当前的底层数组的长度，要至少为 MIN_TREEIFY_CAPACITY = 64
     *
     * 7. 负载因子的初始值是多少 0.75， 负载因子的作用是什么？
     *    影响hashmap扩容的时机，当Hashmap中存放键值对的容量达到 底层数组长度*负载因子时，hashmap需要对底层数组扩容
     *
     *  put 键值对的过程
     *  (1) 在hashmap内部，有一个 hash方法 ，会对传入的key调用这个方法得到一个hash值（int值），这个值会影响键值对在底层数组中的位置
     *  (2) 扩容的时机，当size（元素的数量）>threshold时，要对底层数组进行扩容
     *  (3) 当第一次put键值对时，会调用resize方法，对底层数组进行初始化，初始容量为 DEFAULT_INITIAL_CAPACITY=16
     *      初始的阈值为 16*0.75 = 12， 底层数组的长度为16.
     *      底层数组的长度必须是 2的n次方 （原因，hashmap底层采用了与运算替换掉了取模运算计算key在数组下标）
     *  (4) 当出现hash冲突时，使用连地址方法解决hash冲突，就是把应该插入的键值对，插入到数组下标元素链表的最后一个位置
     */
        public static void main(String[] args) {

            HashMap<Integer, String> map = new HashMap<>(64);

            char c = 'a';
            for (int i = 1; i <= 9; i++) {
                map.put(1+(i-1)*64,""+(c++));
            }

//        map.put(1,"a");
//        map.put(2,"b");
//        map.put(65,"c");
//        map.put(65+64,"d");
//        map.put(17+16+16,"e");
//        map.put(17+16+16+16,"f");
//        map.put(17+16+16+16+16,"g");
//        map.put(17+16+16+16+16+16,"h");
//        map.put(17+16+16+16+16+16+16,"i");
//        map.put(17+16+16+16+16+16+16+16,"j");
//        System.out.println(map.get(1));
//        System.out.println(map.get(17 + 16 + 16 + 16 + 16));


//        System.out.println(map.get(1));
//        System.out.println(map.get(17 + 16 + 16 + 16 + 16));







        }
}
